package com.jxb.five;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 无重复字符的最长子串
 * 输入: s = "abcabcbb"
 * 输出: 3
 *
 * 思路1：
 *  使用滑动时间窗来实现
 *  定义2个指针，i和rix，以及一个map，map用于记录不重复的字符
 *  移动rix，遇到不重复的字符，放入到map中，若map中有重复的字符，就进行删除map中的当前字符，然后i往前移动一位，直至rix指针到达最后一位
 *
 * @author jiaobo
 * @date Created in 2025/1/2 22:25
 **/
public class LongestSubstring_3 {

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(lengthOfLongestSubstring2(s));
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null ||s.length() == 0) {
            return 0;
        }
        //定义2个指针
        int i = 0;
        int rix = -1;
        //定义map
        Set<String> set = new HashSet<>();
        //记录字符串的长度
        int ans = 0;
        while (rix < s.length() - 1) {
            char c = s.charAt(rix + 1);
            if (!set.contains(String.valueOf(c))) {
                set.add(String.valueOf(c));
                rix++;
                ans = Math.max(ans,rix - i + 1);
            }else {
                set.remove(String.valueOf(s.charAt(i)));
                ans = Math.max(ans,rix - i + 1);
                i++;
            }
        }
        return ans;
    }

    //使用hashmap进行优化
    public static int lengthOfLongestSubstringWithMap(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0,start = 0;
        for (int end = 0;end < s.length(); end++) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                start = Math.max(map.get(c) + 1,start);
            }
            max = Math.max(max,end-start + 1);
            map.put(c,end);
        }
        return max;
    }


    public static int lengthOfLongestSubstring2(String s) {
        if (s == null ||s.length() == 0) {
            return 0;
        }
        //定义2个指针
        int i = 0;
        int rix = -1;
        //定义map
        // Set<String> set = new HashSet<>();
        Map<Character, Integer> map = new HashMap<>();
        //记录字符串的长度
        int ans = 0;
        while (rix < s.length() - 1) {
            char c = s.charAt(rix + 1);
            if (!map.containsKey(c)) {
                rix++;
                ans = Math.max(ans,rix - i + 1);
                map.put(c,rix);
            }else {
                Integer index = map.get(s.charAt(i));
                map.remove(s.charAt(i));
                ans = Math.max(ans,rix - i + 1);
                if (index != null) {
                    i = Math.max(i,index + 1);
                }
            }
        }
        return ans;
    }

    public static int lengthOfLongestSubstringWithMap1(String s) {
        HashMap<Character,Integer> map = new HashMap<>();
        int max = 0,start = 0;
        for (int end = 0;end<s.length();end++) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                start = Math.max(map.get(c)+1,start);
            }
            max = Math.max(max,end-start + 1);
            map.put(c,end);
        }
        return max;
    }

}
